//
//  linkedList.cpp
//  labuladong
//
//  Created by 刘振舟 on 2023/5/16.
//

#include "linkedList.h"

ListNode* LinkedListSolution::mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode(-1), *p = dummy;
    ListNode* p1 = list1, *p2 = list2;
    while (p1 && p2) {
        if (p1->val > p2->val) {
            p->next = p2;
            p2 = p2->next;
        } else {
            p->next = p1;
            p1 = p1->next;
        }
        p = p->next;
    }
    
    if (p1) {
        p->next = p1;
    }
    if (p2) {
        p->next = p2;
    }
    return dummy->next;
}

ListNode *LinkedListSolution::partition(ListNode *head, int x) {
        ListNode *dummy1 = new ListNode(-1);
        ListNode *dummy2 = new ListNode(-1);
        dummy2->next = nullptr;
        
        ListNode *p1 = dummy1, *p2 = dummy2, *p = head;
        
        while (p) {
            if (p->val < x) {
                p1->next = p;
                p1 = p1->next;
            } else {
                p2->next = p;
                p2 = p2->next;
            }
            p = p->next;
        }
        
        p2->next = nullptr;
         
        p1->next = dummy2->next;
        return dummy1->next;
}

ListNode* LinkedListSolution::mergeKLists(vector<ListNode*>& lists)
{
    ListNode* dummy = new ListNode(-1), *p = dummy;
    auto comp = [](ListNode*& prev, ListNode*& next) {
        return prev->val > next->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> priorityQueue(comp);
    for (auto& head : lists)
    {
        if (head)
        {
            priorityQueue.push(head);
        }
    }

    while (!priorityQueue.empty())
    {
        auto item = priorityQueue.top();
        priorityQueue.pop();
        p->next = item;
        p = item;
        if (item->next)
        {
            priorityQueue.push(item->next);
        }
    }
    return dummy->next;
}

ListNode* LinkedListSolution::removeNthFromEnd(ListNode* head, int n)
{
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* slow = dummy, * fast = dummy;
    for (size_t i = 0; i < n; i++)
    {
        fast = fast->next;
    }

    while (fast->next)
    {
        slow = slow->next;
        fast = fast->next;
    }
    slow->next = slow->next->next;
    return dummy->next;
}

ListNode* LinkedListSolution::middleNode(ListNode* head)
{
    ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

ListNode* LinkedListSolution::detectCycle(ListNode* head)
{
    ListNode* slow = head, * fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            slow = head;
            while (fast != slow)
            {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

ListNode *LinkedListSolution::getIntersectionNode(ListNode *headA, ListNode *headB) { 
    ListNode* p1 = headA, * p2 = headB;
    
    while (p1 != p2) {
        if (p1) {
            p1 = p1->next;
        } else {
            p1 = headB;
        }
        
        if (p2) {
            p2 = p2->next;
        } else {
            p2 = headA;
        }
    }
    return p1;
}


ListNode *LinkedListSolution::deleteDuplicates(ListNode *head) {
    if (!head) {
        return nullptr;
    }
    ListNode* slow = head, * fast = head;
    while (fast) {
        if (slow->val != fast->val) {
            slow = slow->next;
            slow->val = fast->val;
        }
        fast = fast->next;
    }
    slow->next = nullptr;
    return head;
}

ListNode *successor = nullptr;

ListNode *reverseN(ListNode *head, int n) {
    if (n == 1) {
        successor = head->next;
        return head;
    }
    ListNode *last = reverseN(head->next, n - 1);
    head->next->next = head;
    head->next = successor;
    return last;
}

ListNode *LinkedListSolution::reverseBetween(ListNode *head, int left, int right) { 
    if (left == 1) {
        return reverseN(head, right);
    };
    head->next = reverseBetween(head->next, left - 1, right - 1);
    return head;
}

ListNode *LinkedListSolution::reverseList(ListNode *head) { 
    if (head == nullptr || head->next == nullptr) {
        return head;
    };
    
    ListNode *last = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return last;
}

ListNode *reverse(ListNode *start, ListNode *end) {
    ListNode *prev = nullptr, *cur = start, *next;
    while (cur != end) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

ListNode *LinkedListSolution::reverseKGroup(ListNode *head, int k) { 
    if (head == nullptr) {
        return head;
    };
    ListNode *start = head, *end = head;
    for (int i = 0; i < k; ++i) {
        if (end == nullptr) {
            return head;
        }
        end = end->next;
    }
    ListNode *newStart = reverse(start, end);
    start->next = reverseKGroup(end, k);
    return newStart;
}








